﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _01_Sort
{
   class Sort
   {
      private static void Swap(List<int> list, int aI, int bI)
      {
         int temp = list[aI];
         list[aI] = list[bI];
         list[bI] = temp;
      }

      public static void SelectSort(List<int> list)
      {
         if (list.Count <= 1)
            return;
         for (int i = 0; i < list.Count; i++)
         {
            int minIndex = i;
            for (int j = i; j < list.Count; j++)
               minIndex = (list[minIndex] > list[j]) ? j : minIndex;
            Swap(list, minIndex, i);
         }
      }

      public static void BubbleSort(List<int> list)
      {
         if (list.Count <= 1)
            return;
         for (int i = list.Count - 1; i > 0; i--)
         {
            bool flag = false;
            for (int j = 0; j < i; j++)
            {
               if (list[j] > list[j + 1])
               {
                  Swap(list, j, j + 1);
                  flag = true;
               }
            }
            if (!flag)
               break;
         }
      }

      public static void InsertSort(List<int> list)
      {
         if (list.Count <= 1)
            return;
         for (int i = 0; i < list.Count; i++)
         {
            for (int j = i; j > 0 && list[j] < list[j - 1]; j--)
               Swap(list, j, j - 1);
         }
      }

      private static void Merge(List<int> list, int l, int r, int mid)
      {
         int i = l, j = mid + 1;
         List<int> temp = new List<int>();

         while (i <= mid && j <= r)
         {
            if (list[i] <= list[j])
               temp.Add(list[i++]);
            else
               temp.Add(list[j++]);
         }
         while (i <= mid)
            temp.Add(list[i++]);
         while (j <= r)
            temp.Add(list[j++]);

         i = l;
         for (int k = 0; k < temp.Count;)
            list[i++] = temp[k++];
      }

      private static void _MergeSort(List<int> list, int l, int r)
      {
         if (l < r)
         {
            int mid = l + ((r - l) >> 1);
            _MergeSort(list, l, mid);
            _MergeSort(list, mid + 1, r);
            Merge(list, l, r, mid);
         }
      }

      public static void MergeSort(List<int> list)
      {
         _MergeSort(list, 0, list.Count - 1);
      }

      private static void Partition(List<int> list, int l, int r,
         out int sr, out int br, int pos)
      {
         int val = list[pos];
         int i = l;
         sr = l - 1;
         br = r + 1;
         while (i < br)
         {
            if (list[i] < val)
               Swap(list, i++, sr++ + 1);
            else if (list[i] == val)
               i++;
            else
               Swap(list, i, br-- - 1);
         }
      }

      private static void _QuickSort(List<int> list, int l, int r)
      {
         if (l < r)
         {
            int pos = new Random((int)DateTime.Now.Ticks).Next(l, r + 1);
            int sr = 0, br = 0;
            Partition(list, l, r, out sr, out br, pos);
            _QuickSort(list, l, sr);
            _QuickSort(list, br, r);
         }
      }

      public static void QuickSort(List<int> list)
      {
         _QuickSort(list, 0, list.Count - 1);
      }

      private static void Heapify(List<int> list, int i, int heapSize)
      {
         int left = i * 2 + 1, right = left + 1;
         while (left < heapSize)
         {
            int maxIndex = (right < heapSize && list[right] > list[left]) ? right : left;
            maxIndex = (list[maxIndex] < list[i]) ? i : maxIndex;
            if (i == maxIndex)
               return;
            Swap(list, i, maxIndex);
            i = maxIndex;
            left = i * 2 + 1;
            right = left + 1;
         }
      }

      public static void HeapSort(List<int> list)
      {
         int heapSize = list.Count;
         for (int i = list.Count - 1; i >= 0; i--)
            Heapify(list, i, heapSize);
         while (heapSize > 0)
         {
            Swap(list, 0, --heapSize);
            Heapify(list, 0, heapSize);
         }
      }

      private static int GetMaxDigit(List<int> list)
      {
         int maxNum = list.Max();
         int count = 0;
         while (maxNum != 0)
         {
            maxNum /= 10;
            count++;
         }
         return count;
      }

      private static int GetDigit(int num, int d)
      {
         int count = 0, digit = 0;
         while (count < d)
         {
            digit = num % 10;
            num /= 10;
            count++;
         }
         return digit;
      }

      public static void RadixSort(List<int> list)
      {
         if (list.Count <= 1)
            return;
         int d = GetMaxDigit(list);
         List<Queue<int>> buckets = new List<Queue<int>>();
         for (int i = 0; i < 10; i++)
            buckets.Add(new Queue<int>());

         for (int i = 0; i  < d; i++)
         {
            for (int j = 0; j < list.Count;j++)
            {
               buckets[GetDigit(list[j], i + 1)].Enqueue(list[j]);
            }

            int index = 0;
            for (int j = 0; j < 10; j++)
            {
               while (buckets[j].Count != 0)
                  list[index++] = buckets[j].Dequeue();
            }
         }
      }
   }
}
